package com.leetcode.problems188;


/**
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/
 * @Date 2021/11/20 14:34
 * @Author ghery
 * @Version V1.0
 */
public class Solution {

    /**
     * dp[i][k][0]: 第i天不持有股票，最多进行了k次交易
     *              = Math.max(dp[i - 1][k][0],dp[i - 1][k][1] + prices[i]);
     * dp[i][k][1]: 第i天持有股票，最多进行了k次交易
     *              = Math.max(dp[i - 1][k][1],dp[i - 1][k - 1][0] - prices[i]);
     * @param prices
     * @return
     */
    public int maxProfit(int K,int[] prices) {
        if(prices.length <= 1){
            return 0;
        }
        int[][][] dp = new int[prices.length][ K + 1][2];
        dp[0][0][0] = 0;
        dp[0][0][1] = 0;
        for (int k = 1; k <= K; k++) {
            dp[0][k][0] = 0;
            dp[0][k][1] = -prices[0];
        }

        for (int i = 1; i < prices.length; i++) {
            for (int k = 1; k <= K; k++) {
                dp[i][k][0] = Math.max(dp[i - 1][k][0],dp[i - 1][k][1] + prices[i]);
                dp[i][k][1] = Math.max(dp[i - 1][k][1],dp[i - 1][k - 1][0] - prices[i]);;
            }
        }
        return dp[prices.length-1][K][0];
    }
    public static void main(String[] args) {
        int[] prices = {1,2};
        System.out.println(new Solution().maxProfit(1,prices));
    }
}
